/**
 * @Question.Title: 滑动窗口中位数
 * @Question.No: 480
 * @Author: DQ
 * @Date: 2021-02-04 14:16:37
 * @Description: 
 */
//中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。 
//
// 例如： 
//
// 
// [2,3,4]，中位数是 3 
// [2,3]，中位数是 (2 + 3) / 2 = 2.5 
// 
//
// 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗
//口中元素的中位数，并输出由它们组成的数组。 
//
// 
//
// 示例： 
//
// 给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。 
//
// 
//窗口位置                      中位数
//---------------               -----
//[1  3  -1] -3  5  3  6  7       1
// 1 [3  -1  -3] 5  3  6  7      -1
// 1  3 [-1  -3  5] 3  6  7      -1
// 1  3  -1 [-3  5  3] 6  7       3
// 1  3  -1  -3 [5  3  6] 7       5
// 1  3  -1  -3  5 [3  6  7]      6
// 
//
// 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。 
//
// 
//
// 提示： 
//
// 
// 你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。 
// 与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。 
// 
// Related Topics Sliding Window 
// 👍 239 👎 0

package slidingwindows.leetcode.editor.cn;

import com.dq.utils.CreateArray;

import java.util.*;

public class SlidingWindowMedian {
    public static void main(String[] args) {
        Solution solution = new SlidingWindowMedian().new Solution();
        int[] a = {1,2,3,4,2,3,1,4,2};
        int k = 3;
        double[] res = solution.medianSlidingWindow(a,k);
        System.out.println(Arrays.toString(res));

    }
        //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double[] medianSlidingWindow(int[] nums, int k) {
            double[] res = new double[nums.length - k + 1];
            MediumHeap mh = new MediumHeap(k);
            for(int i = 0; i < k; i++) mh.small.offer(nums[i]);
            for(int i = 0; i < k/2 ;i++) mh.large.offer((mh.small.poll()));
            res[0] = mh.geMedium();
            for(int i = k; i < nums.length; i++){

                mh.del(nums[i-k]);
                mh.put(nums[i]);
                res[i-k+1] = mh.geMedium();
            }
            return res;
        }

        class MediumHeap{
            PriorityQueue<Integer> large = null;
            PriorityQueue<Integer> small = null;
            int k;
            int largeSize;
            int smallSize;
            Map<Integer, Integer> delayMap;
            public MediumHeap(int k){
                this.k = k;
                this.small = new PriorityQueue<Integer>();
                this.large = new PriorityQueue<Integer>((x,y)->y-x);
                this.largeSize = k/2;
                this.smallSize = this.k - this.largeSize;
                this.delayMap = new HashMap<>();
            }
            //放入一个数
            public void put(int num){
//                System.out.println(num);
                if(smallSize==largeSize){
                    large.offer(num);
                    small.offer(large.poll());
                    smallSize++;
                }else {
                    small.offer(num);
                    large.offer(small.poll());
                    largeSize++;
                }
            }
            //删除一个数
            public void del(int num){
                if(delayMap.get(num)==null){
                    delayMap.put(num, 0);
                };
                //放入延迟删除的map
                delayMap.put(num, delayMap.get(num)+1);

                if(largeSize==smallSize){
                    largeSize--;
                    if(large.peek()==num) {
                        large.poll();
                        delayMap.put(num, delayMap.get(num)-1);
                    }else if(large.peek() < num){
                        small.offer(large.peek());
                    }
                }else if(smallSize>largeSize){
                    smallSize--;
                    if(small.peek()==num) {
                        small.poll();
                        delayMap.put(num, delayMap.get(num)-1);
                    }else if(small.peek() > num){
                        large.offer(small.poll());
                    }
                }

            }
            public int getTop(PriorityQueue<Integer> queue){
                int top = queue.peek();
                // 队列顶的数需要删除时，直接删除
                while (delayMap.get(top)!=null&&delayMap.get(top)!=0){
                    delayMap.put(top, delayMap.get(top)-1);
                    queue.poll();
                    top = queue.peek();
                }
                return top;
            }
            //得到中位数
            public double geMedium(){
                if(largeSize==smallSize){
                    return (getTop(small) + getTop(large)) / 2;
                }
                return getTop(small);
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}